<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    // 首先定义节点
    class TreeNode {
        constructor(left, right) {
            /* left,right表示该节点是[left,right]这一段的节点，sum表示这一段节点的和 */
            this.left = left;
            this.right = right;
            this.sum = 0;
            this.lazyTag = false;
            // 在对Tree可以有多种操作的情况下，应该有这个属性，用来保存每个lazyTag自己未下发给子节点的任务
            this.actions;
        }
    }

    // 定义线段树
    class SegTree {
        // 传入一个数组，根据这个数组构建数
        constructor(nums) {
            const len = nums.lenght;
            this.arr = [];
            this.build(1, 0, len - 1, nums);
        }

        build(id, left, right, nums) {
            this.arr[id] = new TreeNode(left, right);
            if (left === right) {
                this.arr[id].sum = nums[left]
                return;
            }
            let mid = (left + right) >> 1;
            this.build(id * 2, left, mid, nums);
            this.build(id * 2 + 1, mid + 1, right, nums);
            this.arr[id].sum = this.arr[id * 2].sum + this.arr[id * 2 + 1].sum;
        }

        // 区间求和
        sumRange(left, right) {
            return this.query(1, left, right);
        }

        // 区间修改
        modify(id, left, right) {
            // 考虑三种情况，分别是整个节点都在区间内和整个节点都不在区间内，以及部分节点在所求区间内
            if (this.arr[id].left >= left && this.arr[id].right <= right) {
                /* 进行自定义的操作 */
                this.arr[id].lazyTag = true;
                /* 如果有多种操作不要忘记将这些行为添加到actions中 */
                return;
            }
            // 如果该节点存在所求区间的子集
            // 首先要对该点进行懒惰标记检测
            this.pushDown(id);
            // 下放标记之后开始继续迭代修改
            if (this.arr[id * 2].right >= left) {
                this.modify(id * 2, left, right);
            }
            if (this.arr[id * 2 + 1].left <= right) {
                this.modify(id * 2 + 1, left, right);
            }
            this.arr[id].sum = this.arr[id * 2].sum + this.arr[id * 2 + 1].sum;
        }

        // 下放懒惰标记给子节点
        pushDown(id) {
            // 如果当前节点已被标记
            if (this.arr[id].lazyTag) {
                /* 
                    在这里应该要根据拖欠的情况，将子节点欠缺的行动补上
                    然后更新好子节点之后，应当将其lazyTag进行处理（标记为true或取反）
                */

                // 最后把父节点的lazyTag设置为false
                this.arr[id].lazyTag = false;
            }
        }

        // 区间查询
        query(id, left, right) {
            // 考虑三种情况，分别是整个节点都在区间内和整个节点都不在区间内，以及部分节点在所求区间内
            if (this.arr[id].left >= left && this.arr[id].right <= right) {
                return this.arr[id].sum;
            }
            if (this.arr[id].right < left || this.arr[id].left > right) {
                return 0;
            }
            // 如果该节点存在所求区间的子集
            // 首先要对该点进行懒惰标记检测
            this.pushDown(id);
            // 下放标记之后开始继续迭代查找
            let res = 0;
            if (this.arr[id * 2].right >= left) {
                res += this.query(id * 2, left, right);
            }
            if (this.arr[id * 2 + 1].left <= right) {
                res += this.query(id * 2 + 1, left, right);
            }
            return res;
        }
    }

    /* 
        总结：
            -   懒惰线段树最大的特点就在于延迟响应，可以在对某个节点进行操作的时候，
                将对其子节点的操作延迟到需要对子节点进行查改行为的时候再实施

            -   打上lazyTag标记的节点的意思是表示这个节点的子节点还未更新，如果需要改查子节点的话，需要对其进行更新

            -   左右节点延迟的操作时一样的，都存储在父节点的actions中
            
    */
</script>

</html>